238

Bioinformatics of the Brain

of similarity search in topological similarity method of network alignment.

Commonly, both of these methods are used with different weights to evaluate

similarity of networks [6].

9.6.1.1

Relation to Bipartite Graph Matching

A matching of a graph G = (V, E) is the set E^′ ∈E such that any edge (u, v) ∈

E^′ does not share any endpoints with any other edge in E^′ and a maximal

matching can not be enlarged. A weighted maximal matching attempts to

find the maximal weighted matching with total weights of matched edges in

a weighted graph where edges have weights associated with them. A detailed

survey of graph matching methods can be found in [20].

A bipartite graph G = (V1 ∪V2, E) has edges only between vertices in V1

and vertices in V2. Matching, unweighted or weighted in a bipartite graph is

similar, edges that are not adjacent are included in the matching. Global align-

ment problem can be related to weighted bipartite graph matching problem

as follows. Let G1 and G2 be the two graphs that are searched for similarity.

A similarity matrix R is built with elements rij showing the weights of sim-

ilarity, using node or topological similarities or both, between the node i in

G1 and node j in G2. Thus, evaluating the similarity of G1 and G2 is reduced

to finding the maximal matching in G = G1 ∪G2 using a suitable algorithm.

Fortunately, finding maximum unweighted or weighted matching in a graph

is one of the rare graph problems that can be solved in polynomial time.

9.6.1.2

Alignment Quality Evaluation

Quality of the discovered similarity may be evaluated using edge correctness

and induced conserved structure parameters. Edge correctness (EC) param-

eter to evaluate the alignment method of two graphs G1 and G2 is given in

Eqn. 9.12 [21].

EC(G1, G2, f) = ^{|f(E1) ∩E2|}

|E1|

(9.12)

where f is the function to relate edges of graph G1 to the edges of graph G2.

This parameter shows the percentage of correctly aligned edges to evaluate

the goodness of the function. The induced conserved structure (ICS) param-

eter is a generalization of the EC parameter as given in Eqn. 9.13 [22]. The

denominator in this equation denotes the size of edges induced in graph G2

by the mapped vertices.

ICS(G1, G2, f) = ^{|f(E1) ∩E2|}

|EG2[f(V1)]|

(9.13)

9.6.2

Alignment of Brain Networks

Graph matching is used in [23] to form a similarity parameter called the

swap distance to quantify the distance between partial functional connectomes